{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Coins to be Added"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumAddedCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #需要添加的硬币的最小数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0 </strong>开始的整数数组 <code>coins</code>，表示可用的硬币的面值，以及一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>如果存在某个 <code>coins</code> 的子序列总和为 <code>x</code>，那么整数 <code>x</code> 就是一个 <strong>可取得的金额 </strong>。</p>\n",
    "\n",
    "<p>返回需要添加到数组中的<strong> 任意面值 </strong>硬币的 <strong>最小数量 </strong>，使范围 <code>[1, target]</code> 内的每个整数都属于 <strong>可取得的金额</strong> 。</p>\n",
    "\n",
    "<p>数组的 <strong>子序列</strong> 是通过删除原始数组的一些（<strong>可能不删除</strong>）元素而形成的新的 <strong>非空</strong> 数组，删除过程不会改变剩余元素的相对位置。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1,4,10], target = 19\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。\n",
    "可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1,4,10,5,7,19], target = 19\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19] 。\n",
    "可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1,1,1], target = 20\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "需要添加面值为 4 、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16] 。 \n",
    "可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= coins.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= coins[i] &lt;= target</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-coins-to-be-added](https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-coins-to-be-added](https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,10]\\n19', '[1,4,10,5,7,19]\\n19', '[1,1,1]\\n20']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAddedCoins(self, coins: List[int], target: int) -> int:\n",
    "        coins.sort()\n",
    "        reachable = 0\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while reachable < target:\n",
    "            if i < len(coins) and coins[i] <= reachable + 1:\n",
    "                reachable += coins[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                reachable += reachable + 1\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAddedCoins(self, coins: List[int], target: int) -> int:\n",
    "        coins.sort()\n",
    "        total = 0\n",
    "        res = 0\n",
    "        for coin in coins:\n",
    "            while total + 1 < coin:\n",
    "                total += total + 1\n",
    "                res += 1\n",
    "                if total >= target:\n",
    "                    return res\n",
    "            total += coin\n",
    "        while total < target:\n",
    "            total += total + 1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAddedCoins(self, coins: List[int], target: int) -> int:\n",
    "        coins.sort()\n",
    "        ans, s, i = 0, 0, 0\n",
    "\n",
    "        while s < target:\n",
    "            if i < len(coins) and coins[i] <= s+1:\n",
    "                s += coins[i]\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                s  += (s + 1)  # 必须添加 s\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAddedCoins(self, coins: List[int], target: int) -> int:\n",
    "        coins.sort()\n",
    "        print(coins, \"T \",target)\n",
    "        s = 0\n",
    "        k = 0\n",
    "        i = 0\n",
    "        while i < target and k < len(coins) :\n",
    "            if  coins[k] <= i+1:\n",
    "                i += coins [k] \n",
    "                k += 1                          \n",
    "            else:                 \n",
    "                if coins [k] >i + 1:\n",
    "                    s +=1\n",
    "                    i = 2*i +1    \n",
    "                   \n",
    "\n",
    "        while(i < target) :\n",
    "            s +=1\n",
    "            i = 2*i +1   \n",
    "\n",
    "        return s\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
